Міністерство освіти і науки України Національний університет “Львівська політехніка” кафедра прикладної математики КУРСОВА РОБОТА з курсу дискретна математика на тему: „Граматики передування”  Зміст 1. Вступ 2. Основні поняття граматики 3. Граматики передування (загальна характеристика) 4. Алгоритм типу «перенос-згортка» 5. Граматики простого передування 6. Граматики розширеного передування 7. Граматики слабкого передування 8. Список використаної літератури Вступ Для створення нових мов програмування необхідно описати правила згідно яких записуються слова мови. Також виникає проблема розпізнавання вхідних слів, а саме чи належать вони даній мові чи ні. Існує декілька методів перевірки належності стрічки до мови, одним з них є алгоритм типу «перенос – згортка». Суть алгоритму полягає у використанні вхідної стрічки, читаючи її з ліва на право, і магазину. На основі того, що знаходиться в магазині і залишилось не опрацьованим на вході, функція f вирішує, перенести даний вхідний символ в магазин чи викликати процедуру згортки. Якщо виконується останнє рішення, то функція g вирішує, яку згортку зробити. Основні поняття граматики Граматика - це математична система, що визначає мову. Одночасно вона є пристроєм , що надає ланцюжкам мови корисну структуру. У граматиці, що визначає мову L, використовуються дві кінцеві непересічні множини символів - множина нетермінальних символів (позначимо N) і множина термінальних символів (позначимо T). З термінальних символів утворюються слова (ланцюжки) обумовленої мови. Основу граматики становить скінченна множина P правил виводу, які описують процес породження ланцюжків мови. Наприклад, правилом може бути пара (AB, CDE). Якщо вже встановлено, що деякий ланцюжок α породжується граматикою (або «виводиться » у ній) і α містить AB, тобто ліву частину цього правила, у якості свого підланцюжка, то можна утворити новий ланцюжок β, замінивши одне входження AB в α на CDE. Тоді говорять, що β виводиться у даній граматиці . Наприклад, якщо ланцюжок FGABH виведений, то FGCDEH теж виведений. Мова, обумовлена граматикою, - це множина ланцюжків, які складаються тільки з терміналів і виводяться, починаючи з одного особливого ланцюжка, що складається з одного виділеного символу, звичайно позначуваного S. Означення. Граматикою називається четвірка G=(N, T, P, S) , де N - скінченна множина нетермінальних символів, або нетерміналів; T - скінченна множина термінальних символів, або терміналів, яка не перетинається з N; P - скінченна підмножина множин (
)*N(
)*((
)*. S- виділений символ з N називаний початковим (або вихідним) символом. Контекстно-вільною (надалі будем позначати КВ) називається граматика, якщо кожне правило з Р має вигляд А→α, де А
N ,α
(
)*; Граматики передування (загальна характеристика) Найпростіший клас алгоритмів типу "перенос - згортка " базується на так званих відношеннях передування. Для граматики передування межі основи праволінійного ланцюжка можна визначити за допомогою деяких відношень між символами, які входять в даний ланцюжок Техніка розбору, орієнтована на відношеннях передування, використовувалась при побудові аналізаторів для мов програмування однієї з перших. З того часу в літературі появилося декілька видів граматик передування. Ми розглянемо оснований на відношеннях передування детермінований аналіз зліва на право, який проводить правий розбір. При цьому будуть введені граматики передування наступних типів: Простого передування, Розширеного передування, Слабкого передування, Змішаної стратегії передування, Операторного передування. Ключ для розуміння методу розбору по відношенням передування дає визначення відношення  (≥)  між    символами граматики, які при перегляді зліва на право праволінійного ланцюжка ...